NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c-part2/11144

Internet Message Format | 1996-08-05 | 1.8 KB

Path: news2.noc.netcom.net!news
From: Tarang Deshpande <[e-mail]>
Newsgroups: comp.lang.c
Subject: Re: REQUEST: Recursive functions
Date: Wed, 20 Mar 1996 08:33:15 -0800
Organization: NETCOM Network Operations
Message-ID: <[e-mail]>
References: <4h7lft$[e-mail]>
NNTP-Posting-Host: daffy.willows.com
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Mailer: Mozilla 2.0GoldB1 (Win95; I)

Michael Talmage wrote:
>
> I need some help to write a recursive function that will move a mouse through
> a maze to find some cheese at the end.  My instructor did not really teach us
> how to write recursive functions in class.  Any help will be appreciated.
>

I'm not going to tell you the answer but here is a quick leson in
recursion.  First of all anything you do recursively can be done
using loops.  But using loops is more complicated and cumbersome whereas
recursion is more elegant and simple.  However this does not mean that
you should always use recusion because recursion make heavy use of the
stack and this can cause you to run out of memory.

What recusion does is to divide the problem into two or more parts.
Each part is still the same problem and hence you can apply the same
solution to each of the parts; to divide them yet again, and so on.
Finally you have divided the problem down to a part for which the
answer is simple.  Then all you have to do is to is to combine the
simple answers for each of the parts you have divide the problem into.

For example, the clasic example, the problem of factorials.

f(x) = x * (x-1) * (x-2) * ... * 1

A standard loop soulution to the problem would be:

for ( f = x--; x; x-- )
    f *= x;

whereas the recusive solution would be:

if ( x <= 1 )
    return ( 1 );
else
    return ( x * factorial ( x - 1 ) );

Hope that helps.